'''
    合并两个有序链表
'''

'''
思路：
    创建一个虚拟头节点a，同时遍历两个链表，按顺序放在a链表后面,然后再分别判断两个链表是否还没遍历完，没遍历完的链接到a表后面
'''


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class ListNode:
    def __init__(self,val=0,next=None):
        self.val = val
        self.next = next

class Solution:
    def trainningPlan(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        n = ListNode(-1)
        l = n
        p,q = l1,l2
        while p and q:
            if p.val >= q.val:
               l.next = q
               q = q.next
            else:
               l.next = p
               p = p.next
            l = l.next
        if q:
            l.next = q
        if p:
            l.next = p
        return n.next

